// 滑动窗口
// 利用 单调性， 使用 同向双指针 的方法进行优化，使得时间复杂度降低 O(N)
// 定义 双指针 用于维护 窗口 的左右边界
// 进窗口 -> 判断是否出窗口，过程中统计结果

// 例题 2：
// 给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

//        示例 1:

//        输入: s = "abcabcbb"
//        输出: 3
//        解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//        示例 2:
//
//        输入: s = "bbbbb"
//        输出: 1
//        解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
//        示例 3:
//
//        输入: s = "pwwkew"
//        输出: 3
//        解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//        请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
//
//        提示：
//
//        0 <= s.length <= 5 * 104
//        s 由英文字母、数字、符号和空格组成

// 解题思路：
// 与例题 1 相同
// 使用哈希表统计字符的个数，也可以使用数组模拟哈希表
// 进窗口：map.put(ch[right], map.getOrDefault(ch[right], 0) + 1);
// 出现重复字符，出窗口：map.put(ch[left], map.get(ch[left]) - 1); left++
// 更新结果

import java.util.HashMap;
import java.util.Map;

public class LengthOfLongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Map<Character, Integer> map = new HashMap<>();
        char[] ch = s.toCharArray();
        int left = 0;
        int right = 0;
        int ret = 0;
        while(right < n){
            // 进窗口
            map.put(ch[right], map.getOrDefault(ch[right], 0) + 1);
            // 出窗口
            while(map.get(ch[right]) > 1){
                map.put(ch[left], map.get(ch[left]) - 1);
                left++;
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
}
